package lru

import "container/list"

//缓存是一个LRU缓存，它对并发访问不是很安全
type Cache struct {
	maxBytes int64//允许使用的最大内存
	nbytes int64//当前已经使用的内存
	ll *list.List//用标准库实现的双向链表
	cache map[string]*list.Element//双向链表中对应的节点的指针
	//删除函数表示某条记录被移出时的回调函数，可以为nil
	OnEvicted func (key string,value Value)
}

type entry struct{//键值对，它是双向链表节点的数据类型，在链表中仍保存每个值对应的key的好处在于淘汰队首节点时，需要用key从字典中删除对应的映射
	key string
	value Value//为了通用性，我们允许值是实现了value的接口的任意类型，该接口只包含了一个方法len()用于返回值所占用的内存大小
}

//这个接口的作用就是使用函数LEN用来判断它花费了多少字节
type Value interface {
	Len() int
}

//方便实例化cache，实现New（）函数
func New(maxBytes int64,onEvicted func(string,Value))*Cache{
	return &Cache{
		maxBytes: maxBytes,
		ll:list.New(),
		cache: make(map[string]*list.Element),
		OnEvicted: onEvicted,
	}
}

//查找功能，查找功能主要有两个步骤，第一步是从字典中找到对应的双向链表的节点，第二步将该节点移动到队尾
//获得键值的值
func (c *Cache)Get(key string)(value Value,ok bool){
	if ele,ok:=c.cache[key];ok{//如果对应的链表节点存在，则将对应节点移动到队尾，并返回查找到的值
		c.ll.MoveToFront(ele)//双向链表作为队列，队首队尾是相对的，这里约定front为队尾,那么back就是队首了
		kv:=ele.Value.(*entry)//类型断言，判断它商标是entry，如果是entry那么就直接转为entry
		return kv.value,true
	}
	return
}

//删除，这里的删除实际上是缓存淘汰。即移出最近最少访问节点（对首）
func (c *Cache)RemoveOldest(){
	ele:=c.ll.Back()//取到队首节点从链表中删除
	if ele!=nil{
		c.ll.Remove(ele)
		kv:=ele.Value.(*entry)
		delete(c.cache,kv.key)//从字典中删除该节点的映射关系
		c.nbytes-=int64(len(kv.key))+int64(kv.value.Len())//更新当前所用的内存
		if c.OnEvicted!=nil{
			c.OnEvicted(kv.key,kv.value)//执行下回调函数
		}
	}
}

//新增/修改
//增加值和value到里面
func (c *Cache)Add(key string,value Value){
	if ele,ok:=c.cache[key];ok{//如果在键值对里面，那么就修改
		c.ll.MoveToFront(ele)
		kv:=ele.Value.(*entry)
		c.nbytes+=int64(value.Len())-int64(kv.value.Len())
		kv.value=value
	}else{//不在，就添加
		ele:=c.ll.PushFront(&entry{key,value})//会把这个entry当作value放进element里面的元素里面，并返回节点
		c.cache[key]=ele//然后添加一下
		c.nbytes+=int64(len(key))+int64(value.Len())
	}
	for c.maxBytes!=0&&c.maxBytes<c.nbytes{//同时修改
		c.RemoveOldest()
	}
}

//我们实现Len()用来获取添加了多少条数据
func (c *Cache)Len()int{
	return c.ll.Len()//返回添加的节点的个数
}